#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ret(nums.size());
        vector<int> dp1(nums.size() + 1);
        vector<int> dp2(nums.size() + 1);
        dp1[0] = 1;
        for (int i = 1; i <= nums.size(); i++)
        {
            dp1[i] = dp1[i - 1] * nums[i - 1];
        }
        dp2[nums.size()] = 1;
        for (int i = nums.size() - 1; i >= 0; i--)
        {
            dp2[i] = dp2[i + 1] * nums[i];
        }
        for (int i = 0; i < nums.size(); i++)
        {
            ret[i] = dp1[i] * dp2[i + 1];
        }
        return ret;
    }
};
int main()
{
    vector<int> nums = { 1,2,3,4 };
    Solution s;
    s.productExceptSelf(nums);
    return 0;
}